package Search;

import java.util.ArrayList;
import java.util.List;

//二分查找,时间复杂度 O(log n)
//前提，数组是有序的
public class BinarySearch {
	public static void main(String[] args) {
		int[] array = {0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 8, 10, 89, 1000, 1234};
		System.out.println(binartSearch(array, 0, array.length - 1, 1));
	}

	/**
	 * 二分查找
	 *
	 * @param array   待查找的数组
	 * @param left    左边的索引
	 * @param right   右边的索引
	 * @param findVal 要查找的值
	 * @return 找到就返回下标，找不到就返回-1
	 */
	public static List binartSearch(int[] array, int left, int right, int findVal) {
		List<Integer> result = new ArrayList<>();
		if (left > right) {
			return result;
		}

		int mid = (left + right) / 2;
		int midVal = array[mid];

		if (findVal > midVal) {
			//向右边递归
			return binartSearch(array, mid + 1, right, findVal);
		} else if (findVal < midVal) {
			//向左边递归
			return binartSearch(array, left, mid - 1, findVal);
		} else {
			int m = mid;
			while (m - 1 >= 0 && array[m - 1] == findVal) {
				m--;
				result.add(m);
			}

			result.add(mid);

			m = mid;
			while (m + 1 <= array.length - 1 && array[m + 1] == findVal) {
				m++;
				result.add(m);
			}
			return result;
		}
	}


}
